package com.LeeCode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 你能从盒子里获得的最大糖果数
 */

public class Code1298 {
    public static void main(String[] args) {
        int[] status = {1, 1, 1};
        int[] candies = {2, 3, 2};
        int[][] keys = {{}, {}, {}, {}};
        int[][] containedBoxes = {{}, {}, {}, {}};
        int[] initialBoxes = {2, 1, 0};

        System.out.println(new Code1298().maxCandies(status, candies, keys, containedBoxes, initialBoxes));
    }

    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        if (initialBoxes == null || initialBoxes.length == 0) return 0;

        int n = status.length;
        boolean[] hasAccess = new boolean[n];
        boolean[] opened = new boolean[n];
        boolean[] usedKey = new boolean[n];

        Queue<Integer> queue = new LinkedList<>();

        // 初始化：标记你能访问的箱子
        for (int box : initialBoxes) {
            hasAccess[box] = true;
            queue.offer(box);
        }

        int ans = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            // 如果已经打开过，跳过
            if (opened[cur]) continue;

            // 是否可以打开这个箱子？
            if (status[cur] == 1 || usedKey[cur]) {
                opened[cur] = true;
                ans += candies[cur];

                // 使用钥匙开箱
                usedKey[cur] = true;
                status[cur] = 1;

                // 打开箱子后，获取里面的钥匙
                for (int key : keys[cur]) {
                    if (!usedKey[key]) {
                        usedKey[key] = true;
                        status[key] = 1;

                        // 如果你有权限访问那个箱子，就加入队列
                        if (hasAccess[key] && !opened[key]) {
                            queue.offer(key);
                        }
                    }
                }

                // 获取嵌套的箱子
                for (int box : containedBoxes[cur]) {
                    if (!hasAccess[box]) {
                        hasAccess[box] = true;
                        if (!opened[box]) {
                            queue.offer(box);
                        }
                    }
                }
            }
        }

        return ans;
    }
}
